/*
 * File: Igral.c
 *
 * Integrantes:
 * @author	Jormar Arellano		(05-37840)	<jormar.arellano@gmail.com>
 * @author	Sabrina Fernández	(05-38163)	<sabrinamfm@gmail.com>
 */

#include "util.h"
#include "Igral.h"
#include "graph.h"
#include "LocalSearch.h"

#include <stdio.h>
#include <stdlib.h>
#include <errno.h>

void igral_defaults() {
    igral_iter = 1000;
    igral_iter_perturb = 1000;
    igral_verbose = 0;

    igral_k1 = 50;
    igral_k2 = 50;
}

Graph *igral_lowest(Graph *graph, ArrayList *l) {
    int i, color;
    Vertex *v;

    for(i=0; i<l->length; i++) {
        v = graph->vertex->data[ *((int *)l->data[i])-1 ];

        for(color=1; vertexHasConflict(v, color); color++);

        if(v->color != color) {
            setColor(graph, v, color);
        }
    }
    return graph;
}

Graph *igral_highest(Graph *graph, ArrayList *l) {
    int i, color, ub;
    Vertex *v;

    ub = getTotalColor(graph);
    for(i=0; i<l->length; i++) {
        v = graph->vertex->data[ *((int *)l->data[i])-1 ];

        for(color=ub-1; vertexHasConflict(v, color); color--);

        if(v->color < color){
            setColor(graph, v, color);
        }
    }
    return graph;
}

void compact_solution(Graph *graph) {
    removeDeadColors(graph);
}

void igral_smallPerturbation(Graph *graph){
    static int stop = 0;
    int newColor, totalColor;
    ArrayList *vcolors;
    Vertex *v;
    int feasible;

    feasible = isFeasibleSolution(graph);
    if(stop == 0 && feasible){
        stop = 1;

        // Cambiamos el color mas alto
        totalColor = getTotalColor(graph);
        vcolors = graph->Vcolors->data[totalColor-1];
        while(vcolors->length){
            v = vcolors->data[0];
            newColor = rand()%(totalColor-1) + 1;
            setColor(graph, v, newColor);
        }

    } else if(rand()%100 < igral_k1 && !feasible){
        // Eliminamos la infactibilidad de los nodos en conflicto con
        // un algoritmo greedy sencillo
        while(graph->conflictVertex->length){
            v = graph->conflictVertex->data[0];

            for(newColor=1; ; newColor++){
                if( !vertexHasConflict(v, newColor) ){
                    setColor(graph, v, newColor);
                    break;
                }
            }
        }
    } else {
        // Manejar infactibilidad
        graph = apply_local_search(graph);
        compact_solution(graph);
    }

    if(rand()%100 < igral_k2) stop = 0;
}

Graph *igral(Graph *graph) {
    int iter;
    ArrayList *l;
    int lastColors=0, currentColors=0, iterLastColors=0;

    printf("FLAG: %d\n", igral_iter);

    l = newNumerationArray(graph->vertex->length);
    for(iter=0, iterLastColors=0; iter<igral_iter; iter++) {
        permuteArray(l);
		graph = igral_lowest(graph, l);
        graph = igral_highest(graph, l);
        compact_solution(graph);

        currentColors = getTotalColor(graph);
        if(currentColors == lastColors){
            iterLastColors++;
        } else {
            iterLastColors=0;
        }

        if(iterLastColors>30){
            igral_smallPerturbation(graph);
        }

        if(isFeasibleSolution(graph) && currentColors<lastColors)
            lastColors = currentColors;
    }
    freeNumerationArray(l);

    return graph;
}

